package 面试刷题.数字马力;


import java.util.ArrayList;

/**
 * https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class ch03_合并k个已排序的链表 {


    public class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    int[] buck = new int[2010];

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        for (ListNode curr : lists) {
            while (curr != null) {
                buck[curr.val + 1000]++;
                curr = curr.next;
            }
        }
        ListNode head = new ListNode(0);
        ListNode pre = head;

        for (int i = 0; i < buck.length; i++) {
            for (int j = 0; j < buck[i]; j++) {
                pre.next = new ListNode(i - 1000);
                pre = pre.next;
            }
        }
        return head.next;
    }

}
